package edu.whu.rose.clock.ssql.util;

import java.util.ArrayList;

public class Path extends DoubleSequentialIntMap {

	private int initPathSize = 2;
	
	private String[][][] rowPaths;
	private int[][] rowPathSizes;
	private int[][] rowPathCapacities;
	
	private String[][][] columnPaths;
	private int[][] columnPathSizes;
	private int[][] columnPathCapacities;
	
	public Path() {
		super();
		
		rowPaths = new String[rowKeySize][rowValueSize][];
		rowPathSizes = new int[rowKeySize][];
		rowPathCapacities = new int[rowKeySize][];
		
		columnPaths = new String[columnKeySize][columnValueSize][];
		columnPathSizes = new int[columnKeySize][];
		columnPathCapacities = new int[columnKeySize][];
	}
	
	public void doubleInsert(int row, int column, String vertex) {
		if (!this.insertToRow(row, column, vertex)) {
			this.insertToColumn(row, column, vertex);
		}
	}
	
	public boolean insertToRow(int row, int column, String vertex) {
		//initialize the parameters
		int low = 0;
		int mid = 0;
		int top = this.getRowKeyCapacity() - 1;
		
		//find the position to insert
		while (low <= top) {
			mid = (low + top) / 2;
			if (row < this.getRowKey(mid)) {
				top = mid - 1;
			}
			else if (row > this.getRowKey(mid)) {
				low = mid + 1;
			}
			else if (row == this.getRowKey(mid)) {
				//the key exists, append the value and vertex
				if (this.appendRowValueAndVertex(mid, column, vertex)) {
					return true;
				}
				return false;
			}
		}
		
		//if the capacity is full, expand the size
		if (rowKeyCapacity == rowKeySize) {
			rowKeySize = 2 * rowKeySize;
			int[] temp1 = rowKeys;
			rowKeys = new int[rowKeySize];
			int[][] temp2 = rowValues;
			rowValues = new int[rowKeySize][];
			int[] temp3 = rowValueSizes;
			rowValueSizes = new int[rowKeySize];
			int[] temp4 = rowValueCapacities;
			rowValueCapacities = new int[rowKeySize];
			int[][] temp5 = rowPathSizes;
			rowPathSizes = new int[rowKeySize][];
			int[][] temp6 = rowPathCapacities;
			rowPathCapacities = new int[rowKeySize][];
			String[][][] temp7 = rowPaths;
			rowPaths = new String[rowKeySize][][];
			for (int i = 0; i < temp1.length; i++) {
				rowKeys[i] = temp1[i];
				rowValues[i] = temp2[i];
				rowValueSizes[i] = temp3[i];
				rowValueCapacities[i] = temp4[i];
				rowPathSizes[i] = temp5[i];
				rowPathCapacities[i] = temp6[i];
				rowPaths[i] = temp7[i];
			}
			for (int i = temp1.length; i < rowKeySize; i++) {
				rowValueSizes[i] = rowValueSize;
			}
		}
		
		//if the key is to be inserted on a not-empty position, move keys and make some room
		for (int i = rowKeyCapacity; i > low; i--) {
			rowKeys[i] = rowKeys[i - 1];
			rowValues[i] = rowValues[i - 1];
			rowValueSizes[i] = rowValueSizes[i - 1];
			rowValueCapacities[i] = rowValueCapacities[i - 1];
			rowPathSizes[i] = rowPathSizes[i - 1];
			rowPathCapacities[i] = rowPathCapacities[i - 1];
			rowPaths[i] = rowPaths[i - 1];
		}
		
		//insert
		rowKeys[low] = row;
		rowValues[low] = new int[rowValueSize];
		rowValues[low][0] = column;
		rowPaths[low][0] = new String[initPathSize];
		rowPaths[low][0][0] = vertex;
		
		//renew the parameters
		rowKeyCapacity++;
		rowValueCapacities[low] = 1;
		rowPathSizes[low] = new int[rowValueSize];
		for (int i = 0; i < rowValueSize; i++) {
			rowPathSizes[low][i] = initPathSize;
		}
		rowPathCapacities[low] = new int[rowValueSize];
		rowPathCapacities[low][0] = 1;
		
		return false;
	}
	
	private boolean appendRowValueAndVertex(int pos, int column, String vertex) {
		for (int i = 0; i < this.getRowValueCapacity(pos); i++) {
			if (column == this.getRowValues(pos)[i]) {
				this.appendRowVertex(i, pos, vertex);
				return true;
			}
		}

		if (rowValueCapacities[pos] == rowValueSizes[pos]) {
			rowValueSizes[pos] = 2 * rowValueSizes[pos];
			int[] temp1 = rowValues[pos];
			rowValues[pos] = new int[rowValueSizes[pos]];
			int[] temp2 = rowPathSizes[pos];
			rowPathSizes[pos] = new int[rowValueSizes[pos]];
			int[] temp3 = rowPathCapacities[pos];
			rowPathCapacities[pos] = new int[rowValueSizes[pos]];
			String[][] temp4 = rowPaths[pos];
			rowPaths[pos] = new String[rowValueSizes[pos]][];
			for (int i = 0; i < temp1.length; i++) {
				rowValues[pos][i] = temp1[i];
				rowPathSizes[pos][i] = temp2[i];
				rowPathCapacities[pos][i] = temp3[i];
				rowPaths[pos][i] = temp4[i];
			}
			for (int i = temp1.length; i < rowValueSizes[pos]; i++) {
				rowPathSizes[pos][i] = initPathSize;
			}
		}
		
		rowValues[pos][rowValueCapacities[pos]] = column;
		rowPaths[pos][rowValueCapacities[pos]] = new String[initPathSize];
		rowPaths[pos][rowValueCapacities[pos]][0] = vertex;
		
		rowPathCapacities[pos][rowValueCapacities[pos]]++;
		rowValueCapacities[pos]++;
		
		return false;
	}
	
	private void appendRowVertex(int i, int j, String vertex) {
		if (rowPathCapacities[i][j] == rowPathSizes[i][j]) {
			rowPathSizes[i][j] = 2 * rowPathSizes[i][j];
			String[] temp = rowPaths[i][j];
			rowPaths[i][j] = new String[rowPathSizes[i][j]];
			for (int k = 0; k < temp.length; k++) {
				rowPaths[i][j][k] = temp[k];
			}
		}
		
		rowPaths[i][j][rowPathCapacities[i][j]] = vertex;
		rowPathCapacities[i][j]++;
	}
	
	public boolean insertToColumn(int row, int column, String vertex) {
		//initialize the parameters
		int low = 0;
		int mid = 0;
		int top = this.getColumnKeyCapacity() - 1;
		
		//find the position to insert
		while (low <= top) {
			mid = (low + top) / 2;
			if (column < this.getColumnKey(mid)) {
				top = mid - 1;
			}
			else if (column > this.getColumnKey(mid)) {
				low = mid + 1;
			}
			else if (column == this.getColumnKey(mid)) {
				//the key exists, append the value and vertex
				if (this.appendColumnValueAndVertex(mid, row, vertex)) {
					return true;
				}
				return false;
			}
		}
		
		//if the capacity is full, expand the size
		if (columnKeyCapacity == columnKeySize) {
			columnKeySize = 2 * columnKeySize;
			int[] temp1 = columnKeys;
			columnKeys = new int[columnKeySize];
			int[][] temp2 = columnValues;
			columnValues = new int[columnKeySize][];
			int[] temp3 = columnValueSizes;
			columnValueSizes = new int[columnKeySize];
			int[] temp4 = columnValueCapacities;
			columnValueCapacities = new int[columnKeySize];
			int[][] temp5 = columnPathSizes;
			columnPathSizes = new int[columnKeySize][];
			int[][] temp6 = columnPathCapacities;
			columnPathCapacities = new int[columnKeySize][];
			String[][][] temp7 = columnPaths;
			columnPaths = new String[columnKeySize][][];
			for (int i = 0; i < temp1.length; i++) {
				columnKeys[i] = temp1[i];
				columnValues[i] = temp2[i];
				columnValueSizes[i] = temp3[i];
				columnValueCapacities[i] = temp4[i];
				columnPathSizes[i] = temp5[i];
				columnPathCapacities[i] = temp6[i];
				columnPaths[i] = temp7[i];
			}
			for (int i = temp1.length; i < columnKeySize; i++) {
				columnValueSizes[i] = columnValueSize;
			}
		}
		
		//if the key is to be inserted on a not-empty position, move keys and make some room
		for (int i = columnKeyCapacity; i > low; i--) {
			columnKeys[i] = columnKeys[i - 1];
			columnValues[i] = columnValues[i - 1];
			columnValueSizes[i] = columnValueSizes[i - 1];
			columnValueCapacities[i] = columnValueCapacities[i - 1];
			columnPathSizes[i] = columnPathSizes[i - 1];
			columnPathCapacities[i] = columnPathCapacities[i - 1];
			columnPaths[i] = columnPaths[i - 1];
		}
		
		//insert
		columnKeys[low] = column;
		columnValues[low] = new int[columnValueSize];
		columnValues[low][0] = row;
		columnPaths[low][0] = new String[initPathSize];
		columnPaths[low][0][0] = vertex;
		
		//renew the parameters
		columnKeyCapacity++;
		columnValueCapacities[low] = 1;
		columnPathSizes[low] = new int[columnValueSize];
		for (int i = 0; i < columnValueSize; i++) {
			columnPathSizes[low][i] = initPathSize;
		}
		columnPathCapacities[low] = new int[columnValueSize];
		columnPathCapacities[low][0] = 1;
		
		return false;
	}
	
	private boolean appendColumnValueAndVertex(int pos, int column, String vertex) {
		for (int i = 0; i < this.getColumnValueCapacity(pos); i++) {
			if (column == this.getColumnValues(pos)[i]) {
				this.appendColumnVertex(i, pos, vertex);
				return true;
			}
		}

		if (columnValueCapacities[pos] == columnValueSizes[pos]) {
			columnValueSizes[pos] = 2 * columnValueSizes[pos];
			int[] temp1 = columnValues[pos];
			columnValues[pos] = new int[columnValueSizes[pos]];
			int[] temp2 = columnPathSizes[pos];
			columnPathSizes[pos] = new int[columnValueSizes[pos]];
			int[] temp3 = columnPathCapacities[pos];
			columnPathCapacities[pos] = new int[columnValueSizes[pos]];
			String[][] temp4 = columnPaths[pos];
			columnPaths[pos] = new String[columnValueSizes[pos]][];
			for (int i = 0; i < temp1.length; i++) {
				columnValues[pos][i] = temp1[i];
				columnPathSizes[pos][i] = temp2[i];
				columnPathCapacities[pos][i] = temp3[i];
				columnPaths[pos][i] = temp4[i];
			}
			for (int i = temp1.length; i < columnValueSizes[pos]; i++) {
				columnPathSizes[pos][i] = initPathSize;
			}
		}
		
		columnValues[pos][columnValueCapacities[pos]] = column;
		columnPaths[pos][columnValueCapacities[pos]] = new String[initPathSize];
		columnPaths[pos][columnValueCapacities[pos]][0] = vertex;
		
		columnPathCapacities[pos][columnValueCapacities[pos]]++;
		columnValueCapacities[pos]++;
		
		return false;
	}
	
	private void appendColumnVertex(int i, int j, String vertex) {
		if (columnPathCapacities[i][j] == columnPathSizes[i][j]) {
			columnPathSizes[i][j] = 2 * columnPathSizes[i][j];
			String[] temp = columnPaths[i][j];
			columnPaths[i][j] = new String[columnPathSizes[i][j]];
			for (int k = 0; k < temp.length; k++) {
				columnPaths[i][j][k] = temp[k];
			}
		}
		
		columnPaths[i][j][columnPathCapacities[i][j]] = vertex;
		columnPathCapacities[i][j]++;
	}
	
	//insert a whole row
	public void insertRow(int key, int[] value, String[][] paths, int vs, int vc, int[] ps, int[] pc) {
		if (rowKeyCapacity == rowKeySize) {
			rowKeySize = 2 * rowKeySize;
			int[] temp1 = rowKeys;
			rowKeys = new int[rowKeySize];
			int[][] temp2 = rowValues;
			rowValues = new int[rowKeySize][];
			int[] temp3 = rowValueSizes;
			rowValueSizes = new int[rowKeySize];
			int[] temp4 = rowValueCapacities;
			rowValueCapacities = new int[rowKeySize];
			String[][][] temp5 = rowPaths;
			rowPaths = new String[rowKeySize][][];
			int[][] temp6 = rowPathSizes;
			rowPathSizes = new int[rowKeySize][];
			int[][] temp7 = rowPathCapacities;
			rowPathCapacities = new int[rowKeySize][];
			for (int i = 0; i < temp1.length; i++) {
				rowKeys[i] = temp1[i];
				rowValues[i] = temp2[i];
				rowValueSizes[i] = temp3[i];
				rowValueCapacities[i] = temp4[i];
				rowPaths[i] = temp5[i];
				rowPathSizes[i] = temp6[i];
				rowPathCapacities[i] = temp7[i];
			}
			for (int i = temp1.length; i < rowKeySize; i++) {
				rowValueSizes[i] = rowValueSize;
			}
		}
		
		rowKeys[rowKeyCapacity] = key;
		rowValues[rowKeyCapacity] = value;
		rowValueSizes[rowKeyCapacity] = vs;
		rowValueCapacities[rowKeyCapacity] = vc;
		
		rowPaths[rowKeyCapacity] = paths;
		rowPathSizes[rowKeyCapacity] = ps;
		rowPathCapacities[rowKeyCapacity] = pc;
		
		for (int i = 0; i < rowValueCapacities[rowKeyCapacity]; i++) {
			for (int j = 0; j < rowPathCapacities[rowKeyCapacity][i]; j++) {
				this.insertToRow(rowValues[rowKeyCapacity][i], key, rowPaths[rowKeyCapacity][i][j]);
			}
		}
		
		rowKeyCapacity++;
	}
	
	//insert a whole column
	public void insertColumn(int key, int[] value, String[][] paths, int vs, int vc, int[] ps, int[] pc) {
		if (columnKeyCapacity == columnKeySize) {
			columnKeySize = 2 * columnKeySize;
			int[] temp1 = columnKeys;
			columnKeys = new int[columnKeySize];
			int[][] temp2 = columnValues;
			columnValues = new int[columnKeySize][];
			int[] temp3 = columnValueSizes;
			columnValueSizes = new int[columnKeySize];
			int[] temp4 = columnValueCapacities;
			columnValueCapacities = new int[columnKeySize];
			String[][][] temp5 = columnPaths;
			columnPaths = new String[columnKeySize][][];
			int[][] temp6 = columnPathSizes;
			columnPathSizes = new int[columnKeySize][];
			int[][] temp7 = columnPathCapacities;
			columnPathCapacities = new int[columnKeySize][];
			for (int i = 0; i < temp1.length; i++) {
				columnKeys[i] = temp1[i];
				columnValues[i] = temp2[i];
				columnValueSizes[i] = temp3[i];
				columnValueCapacities[i] = temp4[i];
				columnPaths[i] = temp5[i];
				columnPathSizes[i] = temp6[i];
				columnPathCapacities[i] = temp7[i];
			}
			for (int i = temp1.length; i < columnKeySize; i++) {
				columnValueSizes[i] = columnValueSize;
			}
		}
		
		columnKeys[columnKeyCapacity] = key;
		columnValues[columnKeyCapacity] = value;
		columnValueSizes[columnKeyCapacity] = vs;
		columnValueCapacities[columnKeyCapacity] = vc;
		
		columnPaths[columnKeyCapacity] = paths;
		columnPathSizes[columnKeyCapacity] = ps;
		columnPathCapacities[columnKeyCapacity] = pc;
		
		for (int i = 0; i < columnValueCapacities[columnKeyCapacity]; i++) {
			for (int j = 0; j < columnPathCapacities[columnKeyCapacity][i]; j++) {
				this.insertToRow(columnValues[columnKeyCapacity][i], key, columnPaths[columnKeyCapacity][i][j]);
			}
		}
		
		columnKeyCapacity++;
	}
	
	public void print() {
		for (int i = 0; i < rowKeyCapacity; i++) {
			for (int j = 0; j < rowValueCapacities[i]; j++) {
				System.out.print(rowKeys[i] + "-->");
				for (int k = 0; k < rowPathCapacities[i][j]; k++) {
					System.out.print(rowPaths[i][j][k] + "-->");
				}
				System.out.println(rowValues[i][j]);
			}
		}
	}
	
	public ArrayList<String> output() {
		ArrayList<String> result = new ArrayList<String>();
		for (int i = 0; i < rowKeyCapacity; i++) {
			for (int j = 0; j < rowValueCapacities[i]; j++) {
				String str = rowKeys[i] + "-->";
				for (int k = 0; k < rowPathCapacities[i][j]; k++) {
					str += rowPaths[i][j][k] + "-->";
				}
				result.add(str + rowValues[i][j]);
			}
		}
		return result;
	}
	
	public String[] getRowPath(int row, int column) {
		return rowPaths[row][column];
	}
	
	public String[] getColumnPath(int column, int row) {
		return rowPaths[column][row];
	}
	
	public int getPathSize(int row, int column) {
		return rowPathSizes[row][column];
	}
	
	public int getPathCapacity(int row, int column) {
		return rowPathCapacities[row][column];
	}
	
	public String[][] getColumnPaths(int key) {
		return columnPaths[key];
	}
	
	public int[] getColumnPathSizes(int key) {
		return columnPathSizes[key];
	}
	
	public int[] getColumnPathCapacities(int key) {
		return columnPathCapacities[key];
	}
	
	public String[][] getRowPaths(int key) {
		return rowPaths[key];
	}
	
	public int[] getRowPathSizes(int key) {
		return rowPathSizes[key];
	}
	
	public int[] getRowPathCapacities(int key) {
		return rowPathCapacities[key];
	}

}
